<?php
/**
 * User: LRZ
 * Date: 2020/1/14
 * Time: 17:04
 */

/**
 *  643.子数组最大平均数 I
 *
 *  标签：数组
 *
 *  给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
 *
 *  示例 1:
 *      输入: [1,12,-5,-6,50,3], k = 4
 *      输出: 12.75
 *      解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
 *   
 *  注意:
 *      1 <= k <= n <= 30,000。
 *      所给数据范围 [-10,000，10,000]。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/maximum-average-subarray-i
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$nums = [1, 12, -5, -6, 50, 3];
$k    = 4;
$res  = findMaxAverage($nums, $k);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function findMaxAverage($nums, $k)
{
    $sum = 0;
    for ($i = 0; $i < $k; $i++) {
        $sum += $nums[$i];
    }
    $max = $sum;
    for ($i = $k, $iMax = count($nums); $i < $iMax; $i++) {
        $sum += $nums[$i] - $nums[$i - $k];
        $max = max($max, $sum);
    }
    return $max / $k;
}